package trie;

/**
 * @desc 域名查找，利用trie树的特点对其进行变种
 * @author hongxingfan
 * @scene 在域名查找
 */
class DomainTree {
	public Node root;

	class Node {
		public String name;
		public String value;
		public int endIndex = 0;
		public Node[] children;
		public int size = 3;
	}

	public DomainTree() {
		root = new Node();
		root.name = "root";
		root.children = new Node[root.size];
	}

	// 插入domain
	public void addNode(String[] domains, Node node, int index) {
		// 递归退出标志
		if (index < 0) {
			return;
		}
		int i = 0, flag = 0; // 找出相等的点后不再添加新节点,直接进入递归
		while (i <= node.endIndex) {
			if (node.children == null)
				node.children = new Node[node.size];
			if (node.children[i] == null)
				node.children[i] = new Node();
			if (domains[index].equals(node.children[i].name)) {
				flag = 1;
				break;
			} else {
				i++;
			}
		}
		if (flag == 0) {
			i--;
			node.children[i] = new Node();
			node.children[i].value = domains[index];
			node.children[i].name = domains[index];
			node.endIndex++;
		}
		addNode(domains, node.children[i], --index);
	}

	// 查找,逻辑一定要清晰，指针怎么走的，都会走那些分支!ss
	public String findNode(String[] domain, Node node, int index) {
		if (index < 0) {
			return node.value;
		}
		int i = 0;
		while (i <= node.endIndex) {
			if (node.children[i] == null)
				return node.value;
			if (!domain[index].equals(node.children[i].value))
				i++;
			else
				break;
		}
		if (i > node.endIndex)
			return "";
		return findNode(domain, node.children[i], --index);
	}
}

public class DomainSearch {

	public static void main(String[] args) {
		DomainTree domain = new DomainTree();

		String[] strs1 = "www.sohu.com".split("\\.");
		domain.addNode(strs1, domain.root, strs1.length - 1);

		String[] strs2 = "auto.sina.com".split("\\.");
		domain.addNode(strs2, domain.root, strs2.length - 1);

		String[] strs3 = "map.baidu.com".split("\\.");
		domain.addNode(strs3, domain.root, strs3.length - 1);

		String[] strs4 = "www.auto.sohu.com".split("\\.");
		String value = domain.findNode(strs4, domain.root, strs4.length - 1);

		System.out.println(value);
	}
}
